#include<iostream>
#include<cstring>
#include<omp.h>
#include<immintrin.h>
#include<sys/time.h>
using namespace std;
const int N = 10000;
int g[N][N], dist[N], st[N];
int thread_count = 7;
void dijkstra(int n) {
	dist[1] = 0;
	for (int i = 0; i < n - 1; ++i) {
		int m_t[thread_count] = { 0 };
		int temp = 0x3f3f3f3f, t = -1;
#pragma omp parallel num_threads(thread_count)
		{
			int id = omp_get_thread_num();
			m_t[id] = -1;
#pragma omp for 
			for (int j = 1; j <= n; ++j)
				if (!st[j] && (m_t[id] == -1 || dist[m_t[id]] > dist[j]))
					m_t[id] = j;
#pragma omp master
			{
				for (int i = 0; i < thread_count; ++i)
					if (m_t[i] != -1 && temp > dist[m_t[i]])
						temp = dist[m_t[i]], t = m_t[i];
				st[t] = 1;
			}
#pragma omp barrier
			int j = 1;
#pragma omp for 
			for (; j + 4 <= n; j += 4) {
				__m128i t1 = _mm_loadu_epi32(&dist[j]);
				__m128i t2 = _mm_loadu_epi32(&g[t][j]);
				__m128i t3 = _mm_set1_epi32(dist[t]);
				t2 = _mm_add_epi32(t2, t3);
				t1 = _mm_min_epi32(t1, t2);
				_mm_storeu_epi32(&dist[j], t1);
			}
			for (; j <= n; ++j)
				dist[j] = min(dist[j], dist[t] + g[t][j]);
		}
	}
}

int main(int argc,char** args) {
	int n, m;
	cin >> n >> m;
	thread_count=args[1][0]-'0';
	for (int i = 1; i <= n; ++i)g[i][i] = 0;
	memset(dist, 0x3f, sizeof dist);
	memset(g, 0x3f, sizeof g);
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (c > g[a][b] || a == b)continue;
		g[a][b] = c;
	}
	
    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	dijkstra(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}